Accurate and reliable time information is necessary for many systems and applications involving distributed resources, including networked systems and processes typified by the Internet. In such systems, different functional elements are required to have their clocks synchronized. Clock synchronization involves two aspects: frequency synchronization and time synchronization. The former means that element clocks run at the same frequency, and the latter means that elements agree at a particular epoch with respect to the coordinated universal time (UTC), i.e., there is no offset between element clocks. For many purposes, it is appropriate to focus on estimating clock offset and to assume higher order effects, such as the frequency offset, can be ignored or provided for separately.
Clock synchronization issues have been extensively addressed in the literature. See, for example, D. Mills, Internet time synchronization: the Network Time Protocol, IEEE Trans. Communications, Vol. 39, No. 10, October 1991; D. Mitra, Network synchronization: analysis of a hybrid of master-slave and mutual synchronization, IEEE Trans. Communications, COM-28, 8 (August 1980), pp. 1245-1259; and N. W. Rickert, Non Byzantine clock synchronization—a programming experiment, ACM Operating Systems Review 22,1 (January 1988), pp. 73-78.
A well-known clock synchronization protocol that has been successfully deployed in the Internet is the Network Time Protocol (NTP), described, for example, in D. Mills, Network Time Protocol (version 3) Specification, Implementation and Analysis RFC 1305, March 1992. One of the most important network clock synchronization issues addressed by NTP is how to use the collected data to estimate the clock offset between a pair of network elements.
In V. Paxson, On Calibrating Measurements of Packet Transit Times, LBNL-41535, ftp://ftp.ee.lbl.gov/papers/vp-clocks-sigmetrics98.ps.gz, March, 1998 (and in a shortened paper with the same title published in Proc. ACM Sigmetrics98, June 22-26, 1998), the author proposed a new algorithm for clock offset estimation. For easy reference, this algorithm will be referred to as the Separate Direction Estimation Algorithm (SDEA). While SDEA can provide improved performance relative to the NTP algorithm, SDEA nevertheless suffers from significant limitations, especially in applying SDEA to contexts in which loading is different for each of the directional links between pairs of network elements.